package com.example.chao.component;

import org.springframework.stereotype.Component;
import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: WangYongChao
 * @Date: 2021/08/05/21:25
 * @Description: 字符串处理
 */
@Component
public class StringManageUtil {
    /**
     * BF算法
     * @param str 原字符串
     * @param sub 子字符串
     * @return 返回s中第一个与p匹配的字符串开始下标
     */
    public static int BF(String str, String sub) {
        int i = 0;
        int j = 0;
        int r = -1;
        boolean f = false;
        while (i < str.length()) {
            while (j < sub.length()) {
                if (str.charAt(i) == sub.charAt(j)) {
                    i++;
                    j++;
                    if (j == sub.length()) {//匹配结束
                        f = true;
                    }
                } else {
                    i = i - j + 1;
                    j = 0;
                    break;
                }
            }
            if (f) {
                r = i - j;
                break;
            } else {
                r = -1;
            }
        }
        return r;
    }



    /**
     * ""kmp字符串匹配算法""
     *
     * @param s 原字符串
     * @param p 子字符串
     * @return 返回s中所有与p匹配的字符串开始下标
     */
    public static List<Integer> KMP(String s, String p) {
        List<Integer> res = new ArrayList<Integer>();
        if (s == null || p == null || s.length() < p.length())
            return res;
        char[] sArr = s.toCharArray();
        char[] pArr = p.toCharArray();
        int[] next = getNext(p);
        int i = 0, j = 0;
        while (i < sArr.length) {
            while (j < pArr.length) {
                //加判断防止i溢出
                if (i >= sArr.length)
                    break;
                //j为-1或匹配，则两数组往后遍历
                if (j == -1 || sArr[i] == pArr[j]) {
                    i++;
                    j++;
                } else {
                    //匹配失败，在next数组中找到应该移动到的位置
                    j = next[j];
                }
            }
            if (j == pArr.length) {
                res.add(i - j);
                j = 0;
            }
        }
        return res;
    }
    //根据模式串计算next数组, next数组记录如果当前j不匹配应该跳到哪个位置
    public static int[] getNext(String p) {
        char[] pArr = p.toCharArray();
        int[] next = new int[pArr.length];
        //如果第一个都不匹配，标记为-1
        next[0] = -1;
        //k表示j不匹配时的下标值
        int j = 0;
        int k = -1;
        while (j < pArr.length - 1) {
            if (k == -1 || pArr[j] == pArr[k]) {
                next[++j] = ++k;
            } else {
                k = next[k];
            }
        }
        return next;
    }


}
